package org.niuke.linkedlist;

import java.util.TreeMap;
import java.util.TreeSet;

public class Solution1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode hou = head;
        ListNode qian = head.next;
        while (qian != null && qian.next != null) {
            hou = hou.next;
            qian = qian.next.next;
        }
        ListNode node = hou.next;
        hou.next = null;
        ListNode n1 = sortInList(head);
        ListNode n2 = sortInList(node);
        ListNode re = new ListNode(-1);
        ListNode h = re;
        while (n1 != null && n2 != null) {
            if (n1.val <= n2.val) {
                re.next = n1;
                re = n1;
                n1 = n1.next;
            } else {
                re.next = n2;
                re = n2;
                n2 = n2.next;
            }
        }
        if (n1 != null) {
            re.next = n1;
        }else {
            re.next = n2;
        }
        return h.next;

    }
}